<html>
<head><meta charset="utf-8"><title>Occurs check · wg-traits · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/index.html">wg-traits</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html">Occurs check</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="202200057"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202200057" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202200057">(Jun 27 2020 at 18:58)</a>:</h4>
<p>So...maybe I'm missing something. But I have no idea what the "occurs check" is</p>



<a name="202200061"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202200061" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202200061">(Jun 27 2020 at 18:58)</a>:</h4>
<p>And googling it gives like no info</p>



<a name="202200088"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202200088" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202200088">(Jun 27 2020 at 18:59)</a>:</h4>
<p>Can someone explain to me what this is?</p>



<a name="202200146"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202200146" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202200146">(Jun 27 2020 at 19:00)</a>:</h4>
<p>(Also, we should add some documentation. Both in the chalk book (or rustc dev guide) and to the <code>OccursCheck</code> struct in chalk-solve)</p>



<a name="202200327"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202200327" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202200327">(Jun 27 2020 at 19:04)</a>:</h4>
<p>It's supposed to prevent the unification of <code>T</code> with <code>Foo&lt;T&gt;</code> because it would lead to infinite recursion.</p>



<a name="202204893"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202204893" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202204893">(Jun 27 2020 at 21:03)</a>:</h4>
<p>Hmm</p>



<a name="202206184"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202206184" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nathan Whitaker <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202206184">(Jun 27 2020 at 21:40)</a>:</h4>
<p>As I understand it, basically during unification when you're trying to unify say an inference variable <code>?X</code> with some <code>T</code> ,  you can just instantiate <code>?X</code> to be <code>T</code> but to avoid the case where <code>T</code> contains <code>?X</code> (say you have <code>T = Vec&lt;?X&gt;</code>), which would create an infinitely recursive type, you check to make sure that <code>?X</code> is not in the set of free variables of <code>T</code></p>



<a name="202206209"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202206209" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nathan Whitaker <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202206209">(Jun 27 2020 at 21:41)</a>:</h4>
<p>So pretty much you're trying to check that the variable does not occur in the type before unifying the variable with the type, hence "occurs check"</p>



<a name="202206258"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202206258" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nathan Whitaker <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202206258">(Jun 27 2020 at 21:42)</a>:</h4>
<p>Hope that makes sense, this is all kind of new for me as well :)</p>



<a name="202206346"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202206346" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202206346">(Jun 27 2020 at 21:46)</a>:</h4>
<p>Yeah, that makes sense</p>



<a name="202206386"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202206386" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202206386">(Jun 27 2020 at 21:46)</a>:</h4>
<p>It's a little weird that it's not really documented anywhere</p>



<a name="202219969"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202219969" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Charles Lew <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202219969">(Jun 28 2020 at 04:54)</a>:</h4>
<p><a href="http://www.cs.union.edu/~striegnk/learn-prolog-now/html/node18.html">http://www.cs.union.edu/~striegnk/learn-prolog-now/html/node18.html</a><br>
<a href="https://www.swi-prolog.org/pldoc/man?predicate=unify_with_occurs_check%2f2">https://www.swi-prolog.org/pldoc/man?predicate=unify_with_occurs_check%2f2</a></p>



<a name="202219980"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202219980" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Charles Lew <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202219980">(Jun 28 2020 at 04:55)</a>:</h4>
<p>Adding a <code>prolog</code> keyword when searching helps.</p>



<a name="202224199"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202224199" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> detrumi <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202224199">(Jun 28 2020 at 07:20)</a>:</h4>
<p>Or Haskell, where the term is used in compiler errors</p>



<a name="202239174"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202239174" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mark Drobnak <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202239174">(Jun 28 2020 at 14:34)</a>:</h4>
<p>Directly from niko himself: <a href="http://smallcultfollowing.com/babysteps/blog/2017/03/25/unification-in-chalk-part-1/#the-occurs-check-preventing-infinite-types">http://smallcultfollowing.com/babysteps/blog/2017/03/25/unification-in-chalk-part-1/#the-occurs-check-preventing-infinite-types</a></p>



<a name="202369526"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Occurs%20check/near/202369526" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Occurs.20check.html#202369526">(Jun 29 2020 at 21:20)</a>:</h4>
<p>You'll find it in most coverage of unification algorithms</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>